// 版权2019 etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package confchange

import (
	"errors"
	"fmt"
	"strings"

	"go.etcd.io/etcd/raft/v3/quorum"
	pb "go.etcd.io/etcd/raft/v3/raftpb"
	"go.etcd.io/etcd/raft/v3/tracker"
)

// 转换器有助于配置更改。它公开了处理
// 简单且共同一致的方法，同时执行适当的验证，允许
// 在无效配置更改影响活动
// 配置之前拒绝这些更改。
type Changer struct {
	Tracker   tracker.ProgressTracker
	LastIndex uint64
}

// EnterJoint验证联合
// 配置的传出（=右）多数配置是否为空，并使用传入（=左）
// 多数配置的副本对其进行初始化。也就是说，它从
// 
// （1 2 3）和（（）
// ）过渡到
// （1 2 3）和（&）。
// 
// 然后将提供的更改应用于传入的多数配置，
// 从而形成一个联合配置，根据Raft论文[1]
// （第4.3节）对应于“新、旧”。
// 
// [1]：https:
func (c Changer) EnterJoint(autoLeave bool, ccs ...pb.ConfChangeSingle) (tracker.Config, tracker.ProgressMap, error) {
	cfg, prs, err := c.checkAndCopy()
	if err != nil {
		return c.err(err)
	}
	if joint(cfg) {
		err := errors.New("config is already joint")
		return c.err(err)
	}
	if len(incoming(cfg.Voters)) == 0 {
		// 为了方便起见，我们允许在空配置中添加节点（测试和
		// 引导），但不能进入联合状态。
		err := errors.New("can't make a zero-voter config joint")
		return c.err(err)
	}
	// 清除传出配置。
	*outgoingPtr(&cfg.Voters) = quorum.MajorityConfig{}
	// 将传入复制到传出。
	for id := range incoming(cfg.Voters) {
		outgoing(cfg.Voters)[id] = struct{}{}
	}

	if err := c.apply(&cfg, prs, ccs...); err != nil {
		return c.err(err)
	}
	cfg.AutoLeave = autoLeave
	return checkAndReturn(cfg, prs)
}

// 从关节配置中退出关节转换。如果配置不是联合的，即如果即将离任的多数
// 此方法是错误的。
// config选民[1]为空，则调用
// 
// 联合配置的传出多数配置将被删除，
// 即传入配置提升为唯一决策者。在Raft论文[1]（第4.3节）的
// 符号中，此方法从
// /`C_{new，old}`转换为`C_unew`。
// 
// 同时，任何阶段学习者（LearnerNext）在前一个传出配置中被重叠投票者阻止添加
// 的内容将被
// 插入学习者。
// 
// [1]：https:
func (c Changer) LeaveJoint() (tracker.Config, tracker.ProgressMap, error) {
	cfg, prs, err := c.checkAndCopy()
	if err != nil {
		return c.err(err)
	}
	if !joint(cfg) {
		err := errors.New("can't leave a non-joint config")
		return c.err(err)
	}
	if len(outgoing(cfg.Voters)) == 0 {
		err := fmt.Errorf("configuration is not joint: %v", cfg)
		return c.err(err)
	}
	for id := range cfg.LearnersNext {
		nilAwareAdd(&cfg.Learners, id)
		prs[id].IsLearner = true
	}
	cfg.LearnersNext = nil

	for id := range outgoing(cfg.Voters) {
		_, isVoter := incoming(cfg.Voters)[id]
		_, isLearner := cfg.Learners[id]

		if !isVoter && !isLearner {
			delete(prs, id)
		}
	}
	*outgoingPtr(&cfg.Voters) = nil
	cfg.AutoLeave = false

	return checkAndReturn(cfg, prs)
}

// Simple执行一系列配置更改，这些更改（总计）使传入的多数配置投票者[0]最多变异一个。如果不是这种情况，如果生成的仲裁为
// 零，或者配置处于联合状态（即存在
// 传出配置），则此方法将返回错误。
func (c Changer) Simple(ccs ...pb.ConfChangeSingle) (tracker.Config, tracker.ProgressMap, error) {
	cfg, prs, err := c.checkAndCopy()
	if err != nil {
		return c.err(err)
	}
	if joint(cfg) {
		err := errors.New("can't apply simple config change in joint config")
		return c.err(err)
	}
	if err := c.apply(&cfg, prs, ccs...); err != nil {
		return c.err(err)
	}
	if n := symdiff(incoming(c.Tracker.Voters), incoming(cfg.Voters)); n > 1 {
		return tracker.Config{}, nil, errors.New("more than one voter changed without entering joint config")
	}

	return checkAndReturn(cfg, prs)
}

// 对配置应用更改。按照惯例，对选民的更改是
// 始终对即将到来的多数选民进行更改[0]。投票者[1]要么
// 为空，要么在联合状态下保留即将离任的多数派配置。
func (c Changer) apply(cfg *tracker.Config, prs tracker.ProgressMap, ccs ...pb.ConfChangeSingle) error {
	for _, cc := range ccs {
		if cc.NodeID == 0 {
			// etcd如果决定（
			// raft的下游）不应用更改，则会将NodeID替换为零，因此我们必须在此处使用显式代码
			// 来忽略这些更改。
			continue
		}
		switch cc.Type {
		case pb.ConfChangeAddNode:
			c.makeVoter(cfg, prs, cc.NodeID)
		case pb.ConfChangeAddLearnerNode:
			c.makeLearner(cfg, prs, cc.NodeID)
		case pb.ConfChangeRemoveNode:
			c.remove(cfg, prs, cc.NodeID)
		case pb.ConfChangeUpdateNode:
		default:
			return fmt.Errorf("unexpected conf type %d", cc.Type)
		}
	}
	if len(incoming(cfg.Voters)) == 0 {
		return errors.New("removed all voters")
	}
	return nil
}

// makeVoter在传入的
// 多数配置中添加或提升给定ID为投票者。
func (c Changer) makeVoter(cfg *tracker.Config, prs tracker.ProgressMap, id uint64) {
	pr := prs[id]
	if pr == nil {
		c.initProgress(cfg, prs, id, false /* isLearner */)
		return
	}

	pr.IsLearner = false
	nilAwareDelete(&cfg.Learners, id)
	nilAwareDelete(&cfg.LearnersNext, id)
	incoming(cfg.Voters)[id] = struct{}{}
}

// 一旦退出活动关节配置，使学习者将给定ID设置为学习者或将其分级为学习者。
// 
// 前者发生在对等方不是传出配置的一部分时，在
// 这种情况下，我们要么在传入
// 配置中添加新学习者，要么降级投票者。
// 
// 后一种情况发生在配置为联合且对等方是传出配置中的
// 投票方时。在这种情况下，我们不希望将同伴
// 添加为学习者，因为这样我们就必须同时跟踪作为投票人的同伴和学习者
// 了。相反，我们将学习者添加到LearnersNext，这样，当传出配置被
// LeaveJoint（）删除时，它将被添加到学习者。
func (c Changer) makeLearner(cfg *tracker.Config, prs tracker.ProgressMap, id uint64) {
	pr := prs[id]
	if pr == nil {
		c.initProgress(cfg, prs, id, true /* isLearner */)
		return
	}
	if pr.IsLearner {
		return
	}
	// 删除传入配置中的任何现有投票者。。。
	c.remove(cfg, prs, id)
	// /。。。但要保存进展。
	prs[id] = pr
	// 如果无法将学习者直接添加到学习者中，请使用LearnersNext，即
	// 如果在传出配置中仍将该对等者作为投票人进行跟踪。它将
	// 在LeaveJoint（）中变成一名学习者。
	// 
	// 否则，请立即添加一名普通学员。
	if _, onRight := outgoing(cfg.Voters)[id]; onRight {
		nilAwareAdd(&cfg.LearnersNext, id)
	} else {
		pr.IsLearner = true
		nilAwareAdd(&cfg.Learners, id)
	}
}

// 从传入配置中将此对等方作为投票者或学习者删除。
func (c Changer) remove(cfg *tracker.Config, prs tracker.ProgressMap, id uint64) {
	if _, ok := prs[id]; !ok {
		return
	}

	delete(incoming(cfg.Voters), id)
	nilAwareDelete(&cfg.Learners, id)
	nilAwareDelete(&cfg.LearnersNext, id)

	// 如果对等方仍然是传出配置中的投票者，请保持进度。
	if _, onRight := outgoing(cfg.Voters)[id]; !onRight {
		delete(prs, id)
	}
}

// initProgress为给定节点或学习者初始化新进度。
func (c Changer) initProgress(cfg *tracker.Config, prs tracker.ProgressMap, id uint64, isLearner bool) {
	if !isLearner {
		incoming(cfg.Voters)[id] = struct{}{}
	} else {
		nilAwareAdd(&cfg.Learners, id)
	}
	prs[id] = &tracker.Progress{
		// 使用最后一个索引初始化进度意味着可以（使用最后一个索引）探测跟随者
		// 。
		// 
		// TODO（待定）：看起来非常乐观。使用第一个索引会更好。这里的一般期望是追随者根本没有日志
		// 因此可能需要快照，尽管应用程序可能
		// 在添加副本之前在带外应用了快照（因此
		// 使第一个索引成为更好的选择）。
		Next:      c.LastIndex,
		Match:     0,
		Inflights: tracker.NewInflights(c.Tracker.MaxInflight),
		IsLearner: isLearner,
		// 当第一次添加节点时，我们应该将其标记为最近处于活动状态。
		// 否则，如果在添加的节点有机会与我们通信之前调用CheckQuorum，CheckQuorum可能会导致我们退出。
		RecentActive: true,
	}
}

// 检查不变量确保配置和进度与
// 彼此兼容。这用于检查转换器初始化时使用的内容
// 以及它返回的内容。
func checkInvariants(cfg tracker.Config, prs tracker.ProgressMap) error {
	// NB:故意允许空配置。在生产中，我们永远不会看到非空配置（我们阻止创建），但我们需要能够*创建*初始配置，例如在引导过程中（或在测试过程中）。我们不必手工编写代码，而是允许
	// 从空配置转换为任何其他合法且非空的
	// 配置。
	for _, ids := range []map[uint64]struct{}{
		cfg.Voters.IDs(),
		cfg.Learners,
		cfg.LearnersNext,
	} {
		for id := range ids {
			if _, ok := prs[id]; !ok {
				return fmt.Errorf("no progress for %d", id)
			}
		}
	}

	// 由于
	// 传出配置中存在冲突的投票者，因此无法直接将任何暂存学习者添加到暂存中。
	for id := range cfg.LearnersNext {
		if _, ok := outgoing(cfg.Voters)[id]; !ok {
			return fmt.Errorf("%d is in LearnersNext, but not Voters[1]", id)
		}
		if prs[id].IsLearner {
			return fmt.Errorf("%d is in LearnersNext, but is already marked as learner", id)
		}
	}
	// 相反，学习者和选民根本不相交。
	for id := range cfg.Learners {
		if _, ok := outgoing(cfg.Voters)[id]; ok {
			return fmt.Errorf("%d is in Learners and Voters[1]", id)
		}
		if _, ok := incoming(cfg.Voters)[id]; ok {
			return fmt.Errorf("%d is in Learners and Voters[0]", id)
		}
		if !prs[id].IsLearner {
			return fmt.Errorf("%d is in Learners, but is not marked as learner", id)
		}
	}

	if !joint(cfg) {
		// 我们强制执行空映射为零而不是零。
		if outgoing(cfg.Voters) != nil {
			return fmt.Errorf("cfg.Voters[1] must be nil when not joint")
		}
		if cfg.LearnersNext != nil {
			return fmt.Errorf("cfg.LearnersNext must be nil when not joint")
		}
		if cfg.AutoLeave {
			return fmt.Errorf("AutoLeave must be false when not joint")
		}
	}

	return nil
}

// 检查并复制跟踪器的配置和进度图（深度足以满足更改者的目的）并返回这些副本。如果checkInvariants返回错误
// 则返回错误。
func (c Changer) checkAndCopy() (tracker.Config, tracker.ProgressMap, error) {
	cfg := c.Tracker.Config.Clone()
	prs := tracker.ProgressMap{}

	for id, pr := range c.Tracker.Progress {
		// 一个浅拷贝就足够了，因为我们只需要对学习者字段进行变异。
		ppr := *pr
		prs[id] = &ppr
	}
	return checkAndReturn(cfg, prs)
}

// checkAndReturn对输入调用checkInvariants并返回结果错误或输入。
func checkAndReturn(cfg tracker.Config, prs tracker.ProgressMap) (tracker.Config, tracker.ProgressMap, error) {
	if err := checkInvariants(cfg, prs); err != nil {
		return tracker.Config{}, tracker.ProgressMap{}, err
	}
	return cfg, prs, nil
}

// err返回零值和一个错误。
func (c Changer) err(err error) (tracker.Config, tracker.ProgressMap, error) {
	return tracker.Config{}, nil, err
}

// nilAwareAdd填充映射条目，必要时创建映射。
func nilAwareAdd(m *map[uint64]struct{}, id uint64) {
	if *m == nil {
		*m = map[uint64]struct{}{}
	}
	(*m)[id] = struct{}{}
}

// nilAwareDelete从映射中删除，如果映射之后为空，则将其自身置零。
func nilAwareDelete(m *map[uint64]struct{}, id uint64) {
	if *m == nil {
		return
	}
	delete(*m, id)
	if len(*m) == 0 {
		*m = nil
	}
}

// symdiff返回两组
// uint64s之间对称差的计数，即len（（l-r）\union（r-l））。
func symdiff(l, r map[uint64]struct{}) int {
	var n int
	pairs := [][2]quorum.MajorityConfig{
		{l, r}, // 计算l中的元素但不计算r中的元素
		{r, l}, // 计算r中的元素但不计算l中的元素
	}
	for _, p := range pairs {
		for id := range p[0] {
			if _, ok := p[1][id]; !ok {
				n++
			}
		}
	}
	return n
}

func joint(cfg tracker.Config) bool {
	return len(outgoing(cfg.Voters)) > 0
}

func incoming(voters quorum.JointConfig) quorum.MajorityConfig      { return voters[0] }
func outgoing(voters quorum.JointConfig) quorum.MajorityConfig      { return voters[1] }
func outgoingPtr(voters *quorum.JointConfig) *quorum.MajorityConfig { return &voters[1] }

// description将配置更改的类型和节点ID打印为
// 以空格分隔的字符串。
func Describe(ccs ...pb.ConfChangeSingle) string {
	var buf strings.Builder
	for _, cc := range ccs {
		if buf.Len() > 0 {
			buf.WriteByte(' ')
		}
		fmt.Fprintf(&buf, "%s(%d)", cc.Type, cc.NodeID)
	}
	return buf.String()
}
